import java.util.Arrays;

public class QuickSort {

    /**
     * 平均时间复杂度&最好情况：O(n*logn)
     * 最坏情况  O(n*n) 序列已经有序（无论是正序还是倒序）
     * 是否稳定  不稳定  int[] arr = {1,2,2,3,3,4};
     * @param array
     * @param startIndex
     * @param endIndex
     */
    public static void quicksort(int[] array, int startIndex, int endIndex) {
        if (startIndex >= endIndex) return;
        //基准值索引
        int pivotIndex = partion(array, startIndex, endIndex);
        quicksort(array, startIndex, pivotIndex - 1);
        quicksort(array, pivotIndex + 1, endIndex);

    }

    public static int partion(int[] array, int startIndex, int endIndex) {
        int pivot = array[startIndex];
        int left = startIndex;
        int right = endIndex;
        while (left != right) {
            //等号不能丢
            while (left < right && array[right] >= pivot) {
                right--;
            }
            while (left < right && array[left] <= pivot) {
                left++;
            }
            if (left < right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
        array[startIndex] = array[left];
        array[left] = pivot;
        return left;
    }

    public static void main(String[] args) {
        int[] array = new int[]{1,3,4,2,0,6,7,9,5,8};
        quicksort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

}
